package _18_剑指OfferII;

import _18_剑指OfferII.datastrcute.ListNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class _026_剑指OfferII重排链表 {

    // 空间复杂度为O(1)
    // 寻找链表的中间节点， 翻转链表，合并链表
    public void reorderList(ListNode head) {
        ListNode midNode = midNode(head);

        ListNode reverseListNode = reverseListNode(midNode);

        mergeListNode(head, reverseListNode);
        midNode.next = null;
    }

    private ListNode midNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode reverseListNode(ListNode listNode) {
        ListNode prev = null;
        while (listNode != null) {
            ListNode temp = listNode.next;
            listNode.next = prev;
            prev = listNode;
            listNode = temp;
        }
        return prev;
    }

    private void mergeListNode(ListNode listNode1, ListNode listNode2) {

        while (listNode1 != null && listNode2 != null) {
            ListNode temp1 = listNode1.next;
            ListNode temp2 = listNode2.next;
            listNode1.next = listNode2;
            listNode2.next = temp1;
            listNode1 = temp1;
            listNode2 = temp2;
        }
    }

    // 利用线性表完成， 链表不支持随机访问，可以转化为线性表完成， 使用队列完成性质差不多一样
    public void reorderList2(ListNode head) {
        List<ListNode> nodes = new ArrayList<>();

        while (head != null) {
            nodes.add(head);
            head = head.next;
        }

        // 双指针记录下标
        int left = 0;
        int right = nodes.size() - 1;
        while (left < right) {
            nodes.get(left++).next = nodes.get(right);
            if (left == right) break;
            nodes.get(right--).next = nodes.get(left);
        }
        nodes.get(left).next = null;
    }

    // 利用双端队列完成
    public void reorderList1(ListNode head) {
        Deque<ListNode> deque = new LinkedList<>();

        while (head != null) {
            deque.add(head);
            head = head.next;
        }

        ListNode prevNode = null;

        while (!deque.isEmpty()) {
            ListNode first = deque.pollFirst();
            ListNode last = deque.pollLast();
            first.next = last;
            if (prevNode != null) {
                prevNode.next = first;
            }
            prevNode = last;
        }
        if (prevNode != null) prevNode.next = null;
    }

}
